package com.example.zzy.zzytest.algo.sort.nlognsort;

import static com.example.zzy.zzytest.test.LeeTest.exch;

/**
 * 希尔排序
 * 对插入排序的改进
 * 先分成步长相等的几组，对小组内进行排序，然后局部有序的情况很适合插入排序，在对全局进行插入
 * <p>
 * 算法步骤：
 * 1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
 * 2.按增量序列个数 k，对序列进行 k 趟排序；
 * 3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。
 * 仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * <p>
 * 改进：在h-子数组中将每个元素换到比他大的元素之前去
 */
public class ShellSort {
    private static void sort(int[] arr) {
        int len = arr.length;
        int step = 1;
        while (step < len / 3) {
            //1,4,13...
            step = 3 * step + 1;
        }

        while (step >= 1) {
            //将step-数组经过插入排序变成有序 step不断变小，直到等于1变成全局有序
            for (int i = step; i < len; i++) {
                for (int j = i; j >= step && arr[j] < arr[j - step]; j -= step) {
                    exch(arr, j, j - step);
                }
            }

            step = step / 3;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{30, 14, 15, 0, 6, 7, 2, 1, 17, 10, 22, 4, 9, 24, 11, 5};
        sort(nums);

        //13-sort         30,14,15,0, 6,7,2,1,17,10,22,4,9,24, 11,5
        //                24,14,15,0, 6,7,2,1,17,10,22,4,9,30, 11,5
        //                24,11,15,0, 6,7,2,1,17,10,22,4,9,30, 14,5
        //                24,11,5, 0, 6,7,2,1,17,10,22,4,9,30, 14,15
        //
        //4 -sort         6 ,11,5, 0,24,7,2,1,17,10,22,4,9,30, 14,15
        //4 -sort         6 ,7,5, 0,24,11,2,1,17,10,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,24,11,5,1,17,10,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,24,11,5,1,17,10,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,17,11,5,1,24,10,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,17,10,5,1,24,11,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,17,10,5,1,24,11,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,17,10,5,1,24,11,22,4,9,30, 14,15
        //4 -sort         6 ,7,2, 0,9 ,10,5,1,17,11,22,4,24,30, 14,15
        //4 -sort         6 ,7,2, 0,9 ,10,5,1,17,11,22,4,24,30, 14,15
        //4 -sort         6 ,7,2, 0,9 ,10,5,1,17,11,14,4,24,30, 22,15
        //4 -sort         6 ,7,2, 0,9 ,10,5,1,17,11,14,4,24,30, 22,15


    }

}
